#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1376. 通知所有员工所需的时间
// 【难度】中等
// 【提交】2025.10.14 https://leetcode.cn/problems/time-needed-to-inform-all-employees/submissions/670590019/
// 【标签】树；深度优先搜索；广度优先搜索
class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<vector<int>> g(n);
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                g[manager[i]].push_back(i);
            }
        }
        function<int(int)> dfs = [&](int u) -> int {
            int res = 0;
            for (auto v : g[u]) {
                res = max(res, dfs(v));
            }
            return informTime[u] + res;
        };
        return dfs(headID);
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 公司有n名员工，每个员工有唯一ID（0到n-1），headID是总负责人ID。
 * manager数组表示每个员工的直接负责人，informTime数组表示每个员工通知下属所需时间。
 * 求从总负责人开始，通知到所有员工所需的最短时间。
 * 模型：树形结构+深度优先搜索，计算从根节点到所有叶子节点的最大路径和。
 * 
 * 二、标准解法状态设计
 * 1. 根据manager数组构建员工关系树（邻接表）。
 * 2. 使用深度优先搜索遍历树结构。
 * 3. 对于每个节点，计算通知所有下属所需的最大时间。
 * 4. 当前节点的总时间 = 通知下属的时间 + 下属中最大的通知时间。
 * 
 * 三、你的实现思路
 * 使用邻接表构建员工关系树，然后使用DFS递归计算从总负责人到所有员工的最大通知时间。
 * 使用lambda表达式定义DFS函数，代码简洁。
 * 
 * 四、逐行注释（带细节提醒）
 * vector<vector<int>> g(n); // 构建邻接表
 * for (int i = 0; i < n; i++) {
 *     if (manager[i] != -1) {
 *         g[manager[i]].push_back(i); // 经理管理下属
 *     }
 * }
 * 
 * function<int(int)> dfs = [&](int u) -> int { // DFS函数
 *     int res = 0; // 记录最大下属通知时间
 *     for (auto v : g[u]) { // 遍历所有下属
 *         res = max(res, dfs(v)); // 递归计算并取最大值
 *     }
 *     return informTime[u] + res; // 当前节点时间 = 通知时间 + 最大下属时间
 * };
 * 
 * return dfs(headID); // 从总负责人开始DFS
 * 
 * 五、正确性证明
 * 算法通过DFS遍历整棵树，对于每个节点：
 * 1. 计算所有下属中最大的通知时间
 * 2. 当前节点的总时间 = 自身通知时间 + 最大下属时间
 * 由于通知是并行进行的，所以总时间取决于最慢的那条路径。
 * 从根节点开始递归计算，最终得到的就是通知所有员工所需的最短时间。
 * 
 * 六、复杂度
 * 时间：O(n)，每个节点只被访问一次。
 * 空间：O(n)，需要邻接表存储树结构，递归栈深度为树的高度。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 算法高效，只需一次DFS遍历；
 *   - 代码简洁，使用lambda表达式使代码更紧凑；
 *   - 逻辑清晰，易于理解。
 * 缺点：
 *   - 递归深度可能受树高度限制，对于极端不平衡的树可能栈溢出；
 *   - 使用递归有一定函数调用开销。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (n == 0) return 0;
 * 2. 可以使用迭代DFS（栈）或BFS（队列）避免递归深度问题；
 * 3. 对于教学场景，可以添加注释解释为什么取最大值（并行通知）。
 * 
 * 九、一句话总结
 * 通过深度优先搜索遍历员工关系树，你的实现高效地计算了通知所有员工所需的最短时间，
 * 展现了树形结构问题中递归思想的优雅应用。
 */